# 假设有从 1 到 n 的 n 个整数。用这些整数构造一个数组 perm（下标从 1 开始），只要满足下述条件 之一 ，该数组就是一个 优美的排列 ：
#  perm[i] 能够被 i 整除
#  i 能够被 perm[i] 整除
#  给你一个整数 n ，返回可以构造的 优美排列 的 数量 。
#
#  示例 1：
# 输入：n = 2
# 输出：2
# 解释：
# 第 1 个优美的排列是 [1,2]：
#     - perm[1] = 1 能被 i = 1 整除
#     - perm[2] = 2 能被 i = 2 整除
# 第 2 个优美的排列是 [2,1]:
#     - perm[1] = 2 能被 i = 1 整除
#     - i = 2 能被 perm[2] = 1 整除
#
#  示例 2：
# 输入：n = 1
# 输出：1
import collections
from typing import List


class Solution:
    def countArrangement3(self, n: int) -> int:
        """
        解法三：状态压缩 + 动态规划
        若 mask 中的第 i 位为 1（从 0 开始编号），则数 i+1 已经被选取，否则就还未被选取
        以 n = 4, n=4,mask=(0110)2为例，这代表数 2,3 都已经被选取并以任意顺序放置在排列中前两个位置
        :param n:
        :return:
        """
        dp = [0] * (1 << n)  # dp[mask] 表示状态为 mask 时的可行方案总数
        # 想要计算 dp[mask] 时，只需要在前 num(mask)−1 位都已经放置了数的情况下，考虑第 num(mask) 位要放置的数即可
        dp[0] = 1
        for mask in range(1, 1 << n):
            num = bin(mask).count("1")
            for i in range(n):
                if mask & (1 << i) and (num % (i + 1) == 0 or (i + 1) % num == 0):
                    dp[mask] += dp[mask ^ (1 << i)]
        return dp[(1 << n) - 1]

    def countArrangement2(self, n: int) -> int:
        """
        解法二：回溯法
        :param n:
        :return:
        """
        match = collections.defaultdict(list)  # 预处理每个位置的符合条件的数有哪些
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if i % j == 0 or j % i == 0:
                    match[i].append(j)
        # print(match)
        visited, res = set(), 0

        def backTrack(index: int) -> None:  # 尝试向位置 index 放入符合条件的数
            if index == n + 1:
                nonlocal res
                res += 1
                return
            for x in match[index]:
                if x not in visited:
                    visited.add(x)
                    backTrack(index + 1)
                    visited.discard(x)
        backTrack(1)
        return res

    def countArrangement1(self, n: int) -> int:
        """
        暴力法，得到所有可能的排列，然后逐个筛选(超时)
        :param n:
        :return:
        """
        allArranges = []
        # 全排列的第一种写法
        arr = [_ for _ in range(1, n + 1)]

        def permutation(index: int) -> None:
            if index == n:
                allArranges.append(list(arr))
            else:
                for i in range(index, n):
                    arr[index], arr[i] = arr[i], arr[index]
                    permutation(index + 1)
                    arr[index], arr[i] = arr[i], arr[index]

        # 全排列的第二种写法
        # arr2 = [[i for i in range(1, n + 1)] for _ in range(1, n + 1)]  # 先提前将每个位置可以放置的所有元素都枚举出来
        # visited = set()
        # allArranges2 = []
        # def permutation2(index: int, singleRes: List[int]) -> None:  # 尝试向位置 index 放入符合条件的数
        #     if index == n:
        #         allArranges2.append(list(singleRes))
        #         return
        #     for num in arr2[index]:
        #         if num not in visited:
        #             visited.add(num)
        #             singleRes.append(num)
        #             permutation2(index + 1, singleRes)
        #             singleRes.pop()
        #             visited.discard(num)

        def check(arr: List[int]) -> bool:
            for index, num in enumerate(arr):
                if num % (index + 1) != 0 and (index + 1) % num != 0:
                    return False
            return True

        res = 0
        permutation(0)  # 得到所有的排列
        print(len(allArranges))
        # permutation2(0, [])  # 得到所有的排列
        # print(len(allArranges2))
        # print(allArranges)
        for a in allArranges:  # 逐个进行筛选
            if check(a):
                res += 1
        return res

    def countArrangement(self, n: int) -> int:
        return self.countArrangement1(n)


if __name__ == "__main__":
    n = 11
    print(Solution().countArrangement(n))
